BOJ20203 Sjekira

풀이

Tree에서 한 edge를 제거하는건 해당 컴포넌트의 최대값만큼의 비용이 듭니다. 이 비용을 최소화하기 위해서는 항상 컴포넌트의 최대값노드와 인접한 간선을 먼저 지워서 최대값 노드를 고립시키는게 최적의 전략인걸 알 수 있습니다. Proof: 어떤 간선 e를 먼저 지우고 최대값 노드를 고립시킨 결과는 간선e비용(=최대값)+(최대값 고립비용)인데, 그 순서를 바꿔주면 최대값 고립비용은 그대로인데 최대값이 고립되었으므로 간선e의 제거비용이 최대값보다 작아집니다. 따라서 최대값을 먼저 고립시키는게 항상 최적임을 알 수 있습니다.

이제 위의 전략을 따라 구현해야하는데, 트리에서 간선을 제거하면서 동시에 각 컴포넌트별로 최대값을 관리해줘야 하므로 구현이 너무 어렵습니다. 거꾸로 모든 간선이 제거된 상태에서 각 간선을 하나씩 추가해가면 Union-Find로 컴포넌트별 최대값을 쉽게 관리해줄 수 있습니다. 이제 남은건 간선삭제순서의 정확히 반대가 되는 간선추가순서를 알아야 하는데, 이건 각 edge가 연결하는 두 정점중에 최대값으로 정렬한 순서가 되는걸 귀납법으로 증명할 수 있습니다.